BOI 3-Day 2-Problem 1

3rd Balkan Olympiad in Informatics
Varna, Bulgaria, 5-11 October 1995

Day 2 - Problem 1 (Deliveries)

A firm occupies a 10-floors building. After finishing the work day, clerk John has to carry identical packages between floors. He starts and ends this job on floor 1 and can carry only one package.

Write a program that finds the minimum number m of the climbed floors and with the corresponding way of traveling.

Input:
The required deliveries are in the text file INPUT.TXT as follows:

First line:	number of deliveries k<=50
Next lines:	2 numbers that determine a delivery, i.e. the floor sending and the floor receiving a package.
For example:	7
	1 10
	3 2
	4 3
	6 7
	8 9
	3 4
	4 3

Output:
The deliveries are numbered in order they appear in the file: 1,2,...,k. Output is in the file in the following format:

First line:	number m
Next lines:	description of John's movements, which are described by triples: b_i, e_i, d_i, where, b_i - number of sending floor e_i - number of receiving floor d_i - number of delivery, which package John has to carry from floor b_i to floor e_i. Number 0 (zero) means that John carries no package at this step.

Here is one possible answer for the given example. The output OUTPUT.TXT consists of:
12
1,6,1
6,7,4
7,6,0
6,10,1
10,8,0
8,9,5
9,4,0
4,3,4
3,4,6
4,3,7
3,2,2
2,1,0

3rd Balkan Olympiad in Informatics Varna, Bulgaria, 5-11 October 1995

Day 2 - Problem 1 (Deliveries)

3rd Balkan Olympiad in Informatics
Varna, Bulgaria, 5-11 October 1995